import javax.swing.*;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 19182
 * Date: 2025-09-12
 * Time: 17:03
 */
public class SortTest4 {
    public void shellSort(int[] arr){
        int gap = arr.length;
        while(gap > 1){
            gap = gap / 2;
            shell(arr, gap);
        }
    }
    private void shell(int[] arr, int gap){
        for(int i = gap; i < arr.length; i++){
            int end = i - gap;
            int tmp = arr[i];
            while(end >= 0){
                if(arr[end] > tmp){
                    arr[end + gap] = arr[end];
                    end -= gap;
                }else{
                    break;
                }
            }
            arr[end + gap] = tmp;
        }
    }
    public void heapSort(int[] arr){
        //建堆
        for(int i = (arr.length - 1 - 1) / 2; i >= 0; i--){
            siftDown(i, arr, arr.length);
        }
        int end = arr.length - 1;
        while (end > 0){
            swap(arr, 0, end);
            siftDown(0, arr, end);
            end--;
        }
    }
    private void siftDown(int parent, int[] arr, int n){
        int child = 2 * parent + 1;
        while(child < n){
            if(child + 1 < n && arr[child + 1] > arr[child]){
                child++;
            }
            if(arr[child] > arr[parent]){
                swap(arr, child, parent);
                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }
        }
    }
    private void swap(int[] tmp, int x, int y){
        int t = tmp[x];
        tmp[x] = tmp[y];
        tmp[y] = t;
    }
    public void quickSort(int[] arr){
        quick(arr, 0, arr.length - 1);
    }
    private void quick(int[] arr, int left, int right){
        if(left >= right){
            return;
        }
        if(right - left + 1 <= 10){
            insertRangeSort(arr, left, right);
        }
        int mid = left + (right - left) / 2;
        int keypos = getThreeMid(arr, left, mid, right);
        swap(arr, left, keypos);
        int par = partitionHoare(arr, left, right);
        quick(arr, left, par - 1);
        quick(arr, par + 1, right);
    }
    private int partitionHoare(int[] arr, int low, int high){
        int key = arr[low];
        int tmp = low;
        while(low < high){
            while(low < high && arr[high] >= key){
                high--;
            }
            while(low < high && arr[low] <= key){
                low++;
            }
            swap(arr, low, high);
        }
        swap(arr, tmp, low);
        return low;
    }
    private int partitionHole(int[] arr, int low, int high){
        int key = arr[low];
        while(low < high){
            while(low < high && arr[high] >= key){
                high--;
            }
            arr[low] = arr[high];
            while(low < high && arr[low] <= key){
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = key;
        return low;
    }
    private int getThreeMid(int[] arr, int left, int mid, int right){
        if(arr[left] < arr[right]){
            if(arr[right] < arr[mid]){
                return right;
            }else if(arr[mid] < arr[left]){
                return left;
            }else{
                return mid;
            }
        }else{
            if(arr[mid] > arr[left]){
                return left;
            }else if(arr[mid] < arr[right]){
                return right;
            }else{
                return mid;
            }
        }
    }
    private void insertRangeSort(int[] arr, int low, int high){
        for(int i = low + 1; i <= high; i++){
            int end = i - 1;
            int tmp = arr[i];
            while(end >= low){
                if(arr[end] > tmp){
                    arr[end + 1] = arr[end];
                    end--;
                }else{
                    break;
                }
            }
            arr[end + 1] = tmp;
        }
    }
    public void quickSortNor(int[] arr){
       int low = 0;
       int high = arr.length - 1;
       int par = partitionHole(arr, low, high);
       Stack<Integer> st = new Stack<>();
       if(par > low + 1){
           st.push(low);
           st.push(par - 1);
       }
       if(par < high - 1){
           st.push(par + 1);
           st.push(high);
       }
       while(!st.empty()){
           high = st.pop();
           low = st.pop();
           par = partitionHole(arr, low, high);
           if(par > low + 1){
               st.push(low);
               st.push(par - 1);
           }
           if(par < high - 1){
               st.push(par + 1);
               st.push(high);
           }
       }
    }
    public void mergeSort(int[] arr){
        mergeSortChild(arr, 0, arr.length - 1);
    }
    private void mergeSortChild(int[] arr, int left, int right){
        if(left >= right){
            return;
        }
        int mid = left + (right - left) / 2;
        //递归
        mergeSortChild(arr, left, mid);
        mergeSortChild(arr, mid + 1, right);
        //合并
        merge(arr, left, mid, right);
    }
    private void merge(int[] arr, int left, int mid, int right){
        int[] tmp = new int[right - left + 1];
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int k = 0;
        while(s1 <= e1 && s2 <= e2){
            if(arr[s1] < arr[s2]){
                tmp[k++] = arr[s1++];
            }else{
                tmp[k++] = arr[s2++];
            }
        }
        while(s1 <= e1){
            tmp[k++] = arr[s1++];
        }
        while(s2 <= e2){
            tmp[k++] = arr[s2++];
        }
        for(int i = 0; i < tmp.length; i++){
            arr[i + left] = tmp[i];
        }
    }
}
